package com.ln.leetcode._1595;

import org.junit.Test;

import java.util.Arrays;
import java.util.List;

/**
 * 1595. 连通两组点的最小成本
 * <p>
 * 给你两组点，其中第一组中有 size1 个点，第二组中有 size2 个点，且 size1 >= size2 。
 * <p>
 * 任意两点间的连接成本 cost 由大小为 size1 x size2 矩阵给出，其中 cost[i][j] 是第一组中的点 i 和第二组中的点 j 的连接成本。如果两个组中的每个点都与另一组中的一个或多个点连接，则称这两组点是连通的。换言之，第一组中的每个点必须至少与第二组中的一个点连接，且第二组中的每个点必须至少与第一组中的一个点连接。
 * <p>
 * 返回连通两组点所需的最小成本。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * <p>
 * 输入：cost = [[15, 96], [36, 2]]
 * 输出：17
 * 解释：连通两组点的最佳方法是：
 * 1--A
 * 2--B
 * 总成本为 17 。
 * 示例 2：
 * <p>
 * <p>
 * <p>
 * 输入：cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
 * 输出：4
 * 解释：连通两组点的最佳方法是：
 * 1--A
 * 2--B
 * 2--C
 * 3--A
 * 最小成本为 4 。
 * 请注意，虽然有多个点连接到第一组中的点 2 和第二组中的点 A ，但由于题目并不限制连接点的数目，所以只需要关心最低总成本。
 * 示例 3：
 * <p>
 * 输入：cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]
 * 输出：10
 * <p>
 * <p>
 * 提示：
 * <p>
 * size1 == cost.length
 * size2 == cost[i].length
 * 1 <= size1, size2 <= 12
 * size1 >= size2
 * 0 <= cost[i][j] <= 100
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-cost-to-connect-two-groups-of-points
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {

    @Test
    public void test() {
        List<List<Integer>> cost = Arrays.asList(
                Arrays.asList(1, 3, 5),
                Arrays.asList(4, 1, 1),
                Arrays.asList(1, 5, 3)
        );
        connectTwoGroups(cost);
    }

    public int connectTwoGroups(List<List<Integer>> cost) {
        // size1: 第一组长度
        // size2：第二组长度
        // m：第二组店集组合
        int size1 = cost.size(), size2 = cost.get(0).size(), m = 1 << size2;
        // 动态规划数组
        int[][] dp = new int[size1 + 1][m];
        // 初始化
        for (int i = 0; i <= size1; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE / 2);
        }
        // 两组点都为空，因此最小连通成本为 dp[0][0]=0。
        dp[0][0] = 0;
        for (int i = 1; i <= size1; i++) {
            // 对所有的点击组合情况开始遍历分析
            for (int s = 0; s < m; s++) {
                // 第二组遍历
                for (int k = 0; k < size2; k++) {
                    // 当点不在本次遍历的点集中，忽略
                    if ((s & (1 << k)) == 0) {
                        continue;
                    }
                    // s ^ (1 << k) ： 点集 s 去除第 k 个点后的剩余点集
                    dp[i][s] = Math.min(dp[i][s], dp[i][s ^ (1 << k)] + cost.get(i - 1).get(k));
                    dp[i][s] = Math.min(dp[i][s], dp[i - 1][s] + cost.get(i - 1).get(k));
                    dp[i][s] = Math.min(dp[i][s], dp[i - 1][s ^ (1 << k)] + cost.get(i - 1).get(k));
                }
            }
        }
        return dp[size1][m - 1];
    }

    private void printDp(int[][] dp) {
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println();
        }
    }
}
